海明码 校验位数公式的理解 |
您所在的位置:网站首页 › 地铁跑酷的验证码是多少 四位数 › 海明码 校验位数公式的理解 |
#问题
设海明码的校验位数为 最初看到公式时我感到很疑惑啊,百思不得其解,主要的问题是最后那个1哪来的。 看着公式望了半天,一点头绪都没有,好脑袋不如烂笔头,于是我开始手写举例试着理解海明码的校验逻辑。 不写不知道,一写吓一跳。写着写着就发现了,原来这个1来的如此妖娆。 #引入(海明码原理介绍)我们先来复习一下二进制的划分,假设现在有七位二进制数据 我们再来看看海明码的纠错方法。 表示序号的三个二进制位,每一个二进制位取值为1的序号个数都是4个(图中列标红)。这冥冥之中的平衡一定可以好好利用。 我们分别把二进制3-1列取值为1的序号纳入集合A、B、C。 则集合取值 A={7,6,5,4} B={7,6,3,2} C={7,5,3,1} 有一种大家很熟悉,校验一个序列值的方法叫做奇偶校验,偶校验计算方式是序列中所有值异或为0。 如果我们按照A、B、C的集合来分类,每个集合都进行偶校验,就可以得到3个偶校验值,它们需要等于0。由于 根据异或运算的性质,自己与自己本身异或为0。所以可以得到A、B、C的计算公式 海明码考虑的情况是一位纠错。当某一位出错后,A、B、C和它们对应集合数据位的异或就不再是本身与本身的异或,并且最终结果会变为1。 也就是说,接收到数据后,若 比如 如下图,红色方块代表本列有出错元素,A列确定了 在上面讲述海明码纠错过程中,可能有同学已经发现问题所在了。 我们新增了三位校验位,可是只对七位数进行了纠错。 所以公式里的那个1,其实来自于我们没有画出的序号0! 我们回望A、B、C的分类,每一集合都有4个元素,看似非常规律,似乎冥冥之中决定了我们可以使用海明码这样的纠错方式。 偏偏卦不可算尽,虽然每集合都有4个元素,但元素的分布律不是均等的,不仅不是均等的,还遗漏了一个0。 所以 同时我们需要将校验位加入传输数据,也就是真正的有效数据 #ps 会什么会少一个呢?其实很简单,只要理清楚概念。k个校验位,输出的序列(比如ABC),含义是第ABC(二进制)个序号的数值有错,而不是总共有多少个数字之类。所以看看000代表的含义就知道少掉的一种情况去哪了——它代表序列校验正确。 #pps 海明码校验位的位置在这个问题上没有啥作用,最初我觉得它一定有什么深层含义,想了半天也没想出什么 #ppps 或许以后有时间还可以写篇博客,叫做《海明码的哲学原理》。
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |